The invention relates to data compression. More specifically, the invention relates to the generation of embedded bitstreams.
Data compression is often used for reducing the cost of storing large data files on computers as well as reducing the time for transmitting large data files between computers. In the so-called xe2x80x9ctransform methodsxe2x80x9d data is transformed into coefficients that represent the data in a frequency domain. Coefficients may be quantized (lossy compression) without significantly affecting the quality of data that is reconstructed. Redundancy in the coefficients may then be reduced or eliminated (lossless compression) without affecting quality of the reconstructed data.
One well known class of transforms are Wavelet transforms. The Wavelet transforms may be used to perform subband decomposition and produce coefficients that describe the data in a hierarchical multiscale representation. Wavelet transforms have proven useful for the compression of images and the analysis of signals. They have been proposed as the transform for the emerging JPEG-2000 standard.
Among the advantages of the Wavelet transforms, the transform coefficients can be ordered in a hierarchical structure and transmitted in an xe2x80x9cembedded bitstream.xe2x80x9d The embedded bitstream has a property whereby prefixes of the bitstream yield a continuum of lower rate descriptions of the data at the highest possible levels of quality. If the embedded bitstream is truncated during transmission of image data, for instance, the information already transmitted will allow an entire image to be reconstructed. The quality of the reconstructed image is dependent upon the amount information transmitted. If an embedded bitstream is truncated, a complete image of reduced quality can be reconstructed from the transmitted bits. In contrast, truncation of a non-embedded transmission might only allow several rows of an image to be reconstructed.
As additional information is transmitted, the quality of the reconstructed image is improved. If the entire bitstream is transmitted without truncation, a lossless or near-lossless image can be reconstructed.
The transmission just described is often referred to as a progressive-by-quality image transmission. The coefficients are described by bit-planes, and the most significant coefficient bits (that is, the coefficient bits conveying the most important information) are transmitted first.
Another type of transmission is often referred to as a progressive-by-resolution transmission. The progressive-by-resolution transmission involves ordering the coefficients according to different levels of image resolution. The different levels are identified by markers in the embedded bitstream. A computer may use the markers to parse the bitstream and transmit the data for the coefficients corresponding to a resolution that is specified by the receiving computer. The receiving computer can reconstruct an image according to the specified resolution.
A number of coding algorithms have been proposed for ordering the description of transform coefficients such that the retained number of bits of the description can produce the best quality image. Algorithms have been proposed by Shapiro (the xe2x80x9cZerotreexe2x80x9d algorithm) and Said-Pearlman (the xe2x80x9cSPIHTxe2x80x9d algorithm) among others.
There are a number of problems associated with Zerotree and SPIHT algorithms. Both the Zerotree and SPIHT algorithms are based on the construction of a data structure known as a Zerotree. The Zerotree data structure is complex and memory-intensive. The encoding of quantized coefficient bit-planes relies on the use of a complex arrangement of lists and pointers.
Moreover, the Zerotree and SPIHT algorithms minimize image distortion only at bit-plane boundaries. As long as the transmission is truncated at a bit-plane boundary, the image distortion will be minimized. However, if a transmission is truncated at a point other than a bit-plane boundary, the image distortion will not be minimized.
Very often, however, the bit rate of the transmission is not controllable such that the transmission is truncated at a bit-plane boundary. For example, bit rate control might depend upon buffer size in a client. The transmission will be truncated when the buffer is full. Thus, the bit rate will depend upon the size of the buffer in the client.
Truncation of a progressive quality transmission might also occur if a network goes down. Again, the truncation might not occur at a bit-plane boundary. Thus, the image distortion might not be minimized given the amount of information that was transmitted.
Additionally, the Zerotree coders do not provide a clean separation between modeling, ordering, coding and algorithmic components. Consequently, it is difficult to tailor the Zerotree coders to satisfy certain constraints on memory and complexity. Additionally, it is difficult for Zerotree coders to provide a single bitstream that can be parsed efficiently to address both progressive-by-quality and progressive-by-resolution transmissions. Zerotree coders do not directly yield resolution-scalable bitstreams that allow for efficient progressive-by-resolution transmissions. Modifying the coding for the progressive-by-resolution transmission results in a sacrifice in performance of the progressive-by-quality transmission.
There is a need for ordering the description of the transform coefficients in a relatively simple and fast manner and for reducing image distortion over a wider range of bit rates. Overall, there is a need for a coder that is less complex than a Zerotree coder. There is also a need for a coder that has a clean separation between modeling, ordering, coding and algorithmic components. Finally, there is a need for a decoder capable of decoding bitstreams that have been encoded by such a coder.
The present invention may be regarded as a decoder that can reconstruct data from an encoded bitstream. The decoder reads encoded subsequences in the bitstream as ordered; decodes at least some of the ordered subsequences; and combines bits of the subsequences to obtain the reconstructed data. The subsequences are read in order of decreasing expected distortion reduction per expected bit of description.
Other aspects and advantages of the present invention will become apparent from the following detailed description, taken in conjunction with the accompanying drawings, illustrating by way of example the principles of the invention.